#pragma once
#include<iostream>
using namespace std;
#include<vector>
#include"Maxheap.hpp"
class HTNode
{
public:
	HTNode(const int& weight, const char& C)
	{
		this->C = C;
		this->Weight = weight;
		this->Lchild = this->Rchild = this->parent = NULL;
	}
	unsigned int Weight;
	char C;	
	HTNode *parent,*Lchild,*Rchild;
};

class Weightcomptare
{
public:
	bool operator()( HTNode *a,  HTNode * b)const
	{
		return a->Weight < b->Weight;
	}
};



class HuffmanCoding
{
public:
	
	~HuffmanCoding();

	vector<pair<char, string>> MyHuffmanCoding(const vector<pair<int, char>>& w);
private:
	HTNode* HuffmanTree;
	void clear(HTNode* Tree)
	{
		if (!Tree)return;
		clear(Tree->Lchild);
		clear(Tree->Rchild);
		delete Tree;
	}
};




HuffmanCoding::~HuffmanCoding()
{
	this->clear(this->HuffmanTree);	
}


vector<pair<char, string>> HuffmanCoding::MyHuffmanCoding(const vector<pair<int,char>> &w)
{
	HTNode min(0, 0);
	Maxheap<HTNode*, Weightcomptare> heap(&min);
	
	for (vector<pair<int, char>>::const_iterator it = w.begin(); it < w.end(); it++)
	{
		HTNode* tmp = new HTNode(it->first, it->second);
		heap.insert(tmp);
	}
	vector<HTNode*> leaf;
	while (heap.Size()!=1)
	{
		HTNode* Min1 = heap.pop().second;
		if (Min1->C)leaf.push_back(Min1);
		HTNode* Min2 = heap.pop().second;
		if (Min2->C)leaf.push_back(Min2);
		HTNode* Head = new HTNode(Min1->Weight+ Min2->Weight,0);
		Head->Lchild = Min1;
		Head->Rchild = Min2;
		Min1->parent = Min2->parent = Head;
		heap.insert(Head);
	}
	this->HuffmanTree = heap.pop().second;
	
	vector<pair<char, string>> MyHuffmanCoding;

	for (vector<HTNode*>::const_iterator it = leaf.begin(); it < leaf.end(); it++)
	{
		HTNode* leaf1 = *it;
		pair<char, string> Code;
		Code.first = leaf1->C;
		while (leaf1->parent!= NULL)
		{
			if (leaf1->parent->Lchild == leaf1)
			{

				Code.second.insert(0, "0");
			}
			else
			{
				Code.second.insert(0, "1");
			}
			leaf1 = leaf1->parent;
		}
		MyHuffmanCoding.push_back(Code);
	}
	return MyHuffmanCoding;
}